Zápočet 10. 1. 2011

Varianta A

  • Napište TS, který rozpoznává následující jazyk: 1x+101x+21^{x+1}01^{x+2}

  • Ukažte, že f(x):=x!f(x):=x! je PRF

  • Ukažte, že existuje nn, pro které Wn={k∗n∣k∈N}W_n=\{k*n|k\in\mathbb{N}\}. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.)

  • Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný

Varianta B

  • Napište TS, který rozpoznává jazyk 12x,x>=01^{2^x}, x >= 0. Stačil popis/postup.

  • Ukažte, že 2x,x>=02^x, x>=0 je PRF. (odvození)

  • Ukažte, že existuje nn, pro které Wn={nk∣k∈N}W_n=\{n^k | k \in\mathbb{N}\}.

  • Ukažte, že rozvrhování je NPC.